package NowCoder.Mathematics;
import java.util.*;

/**
 * 链接：https://www.nowcoder.com/questionTerminal/c0a4b917a15f40a49ca10532ab9019fb?f=discussion
 * 来源：牛客网
 *
 * 斐波那契凤尾
 * 时间限制：C/C++ 3秒，其他语言6秒 空间限制：C/C++ 32M，其他语言64M
 * NowCoder号称自己已经记住了1-100000之间所有的斐波那契数。
 * 为了考验他，我们随便出一个数n，让他说出第n个斐波那契数。当然，斐波那契数会很大。因此，如果第n个斐波那契数不到6位，则说出该数；否则只说出最后6位。
 *
 * 输入描述:
 * 输入有多组数据。
 * 每组数据一行，包含一个整数n (1≤n≤100000)。
 *
 *
 * 输出描述:
 * 对应每一组输入，输出第n个斐波那契数的最后6位。
 * 示例1
 * 输入
 * 1<br/>2<br/>3<br/>4<br/>100000
 * 输出
 * 1<br/>2<br/>3<br/>5<br/>537501
 */
public class 斐波那契凤尾_编程_2_7_4 {
    //TODO:请重新做这一道题
    public static long[] fibs = new long[100001];
    public static void main(String[] args){

        Scanner sc = new Scanner(System.in);

        //生成fib
        fibs[0] = 1;
        fibs[1] = 1;
        //标记结果是否达到7位数，因为7位数后需输出后六位，含0也需输出
        int flag = 0;
        for (int i = 2; i < fibs.length; i++) {
            long ret = fibs[i - 1] + fibs[i - 2];
            fibs[i] = ret % 1000000;
            if (flag == 0 && ret >= 1000000) flag = i;
        }

        while (sc.hasNext()) {
            int n = sc.nextInt();
            if (n < flag) System.out.println(fibs[n]);
            else System.out.printf("%06d\n", fibs[n]);
        }
    }
}
